/*
https://leetcode.cn/problems/Za25hA/solution/suan-fa-xiao-ai-li-kou-bei-li-jie-zhen-t-hdcb/
 */
import java.util.*;

public class SolutionLCP21 {
    public int chaseGame(int[][] edges, int startA, int startB) {
        int[] first=new int[edges.length+1];
        Arrays.fill(first,-1);
        int[] next=new int[edges.length*2];
        int[] go=new int[edges.length*2];
        int count=0;
        for (int[] edge : edges) {
            next[count]=first[edge[0]];
            first[edge[0]]=count;
            go[count]=edge[1];
            count++;
            next[count]=first[edge[1]];
            first[edge[1]]=count;
            go[count]=edge[0];
            count++;
        }
        int[] visit=new int[edges.length+1];
        Stack<Integer> stack=new Stack<>();
        List<Integer> list=new ArrayList<>();
        stack.push(1);
        dfs(1,stack,visit,first,next,go,list);
        int[] disA=bfs(startA,first,next,go);
        int[] disB=bfs(startB,first,next,go);
        int max=0;
        disA[0]=-1;
        for (int i=1;i<=edges.length;i++){
            if (disA[i]-disB[i]>1 && disA[i]>disA[max]){
                max=i;
            }
        }
        if (max==0){
            return 1;
        }
        if (list.size() != 3) {
            for (Integer integer : list) {
                if (integer == startB) {
                    return -1;
                }
            }
            for (Integer integer : list) {
                if (disA[integer] - disB[integer] > 1) {
                    return -1;
                }
            }
        }
        return disA[max];
    }

    private int[] bfs(int k, int[] first, int[] next, int[] go) {
        int[] dis=new int[first.length];
        Arrays.fill(dis,Integer.MAX_VALUE);
        dis[k]=0;
        Queue<Integer> queue=new LinkedList<>();
        queue.add(k);
        while (!queue.isEmpty()){
            int p=queue.poll();
            int v=first[p];
            while (v!=-1){
                if (dis[go[v]]>dis[p]+1){
                    dis[go[v]]=dis[p]+1;
                    queue.add(go[v]);
                }
                v=next[v];
            }
        }
        return dis;
    }

    private void dfs(int now, Stack<Integer> stack, int[] visit, int[] first, int[] next, int[] go,List<Integer> list) {
        if (visit[now]==1){
            while (stack.peek()!=now){
                list.add(stack.pop());
            }
            list.add(now);
        }else {
            int last=stack.isEmpty()?-1:stack.peek();
            visit[now]=1;
            stack.push(now);
            int p=first[now];
            while (p!=-1){
                if (go[p]!=last){
                    dfs(go[p],stack,visit,first,next,go,list);
                    if (list.size()!=0){
                        return;
                    }
                }
                p=next[p];
            }
            visit[now]=0;
            stack.pop();
        }
    }

    public static void main(String[] args) {
        System.out.println(new SolutionLCP21().chaseGame(new int[][]{{1,2},{2,3},{3,4},{4,1},{2,5},{5,6}},3,5));
    }
}
